package 动态规划.递归参数思考型;

public class leetcode122买卖股票的最佳时机 {
		
	public static void main(String []args) {
		int prices[] = {7,1,5,3,4,6};
		System.out.println(solution(prices));
		System.out.println(dp1(prices));
	}
	
	
	public static int solution(int prices[]) {
		int len = prices.length;
		if(len == 1)
			return 0;
		
		return recursion1(0,0,prices,len);
	}
	
	/**
	 *  index 表示 从 第 index 天开始 玩股票
	 *  而 当前层 递归 返回的结果就是： 从 index 天开始玩股票的 最大收益值！
	 *  而要求的 结果就是从 ，第 0天 开始玩股票的 最大收益！
	 *  注意这个递归的顺序！
	 */
	public static int recursion(int index,int status,int prices[],int len) {
		if(index == len)
			return 0;
		int ans = recursion(index + 1,status,prices,len);
		int ans1 = 0;
		// 当前没有持有股票 ，可以 买入当前天的股票， 但是要 支付当前股票的 一个价钱
		if(status  == 0) {
			ans1 = recursion(index + 1,1,prices,len) - prices[index];
		}
		// 当前 天 是 持有 股票， 可以把 股票 卖掉
		else {
			ans1 = recursion(index + 1,0,prices,len) + prices[index];
		}
		return Math.max(ans, ans1);
	}
	// 另外 一种形式
	public static int recursion1(int index,int status,int prices[],int len) {
		if(index == len)
			return 0;
//		int ans = recursion(index + 1,status,prices,len);
		int ans = 0;
		int ans1 = 0;
		// 当前没有持有股票 ，可以 买入当前天的股票， 但是要 支付当前股票的 一个价钱
		if(status  == 0) {
			ans = recursion1(index + 1,status,prices,len);
			ans1 = recursion1(index + 1,1,prices,len) - prices[index];
//			return Math.max(ans, ans1);
		}
		// 当前 天 是 持有 股票， 可以把 股票 卖掉
		else {
			ans = recursion(index + 1,status,prices,len);
			ans1 = recursion1(index + 1,0,prices,len) + prices[index];
		}
		return Math.max(ans, ans1);
	}
	
	
	/**
	 * 上面那个 暴力递归的 dp 版本
	 * 失败版本！
	 */
	public static int dp(int prices[]) {
		int len = prices.length;
		int dp [][] = new int [len + 1][2];
		dp[len][0] = 0;
		dp[len][1] = 0;
		
		// 手动维护 这个状态变量！
		int status = 0;
		
		for(int index = len -1 ;index >= 0 ;index --) {
			dp[index][status] = dp[index + 1][status];
			if(status == 0) {
				dp[index][status] = Math.max(dp[index][status], dp[index + 1][1] - prices[index]);
				status = 1;
			}
			else {
				dp[index][status] = Math.max(dp[index][status] ,dp[index + 1][0] + prices[index]);				
				status = 0;
			}
		}
		//返回暴力递归  起初传入的 参数 
		return dp[0][0];
	}
	
	
	public static int dp1(int prices[]) {
		int len = prices.length;
		int dp [][] = new int [len + 1][2];
		dp[len][0] = 0;
		dp[len][1] = 0;
		
		// 手动维护 这个状态变量！
//		int status = 0;
		
		for(int index = len -1 ;index >= 0 ;index --) {
			dp[index][0] = Math.max(dp[index + 1][0], dp[index + 1][1] - prices[index]);
			dp[index][1] = Math.max(dp[index + 1][1],dp[index + 1][0] + prices[index]);
		}
		//返回暴力递归  起初传入的 参数 
		System.out.println(dp[0][1]);
		return dp[0][0];
	}
	
	
	
}
